Multi-tone-based communication systems such as Digital Subscriber Line (DSL) systems are widely used as a last-mile solution to provide internet access to end users. In these systems, data is transmitted through the copper pairs traditionally used only for telephony. By using the existing infrastructure to provide broadband access, DSL systems are an attractive and cost-effective solution to last-mile access. Example DSL technologies (sometimes called xDSL) include High Data Rate Digital Subscriber Line (HDSL), Asymmetric Digital Subscriber Line (ADSL), a version of DSL with a slower upload speed, Very-high-bit-rate Digital Subscriber Line (VDSL).
The copper pairs used by DSL systems are usually deployed in binders, which may contain dozens of copper pairs. The proximity of the pairs results in electromagnetic coupling, so that signals from one line interfere with the others. This impairment is known as crosstalk, and is one of the main factors limiting the achievable data rates and reach in DSL systems. Crosstalk can be interpreted as the signal of one line leaking to all neighbouring lines as shown in FIG. 1. In fact, crosstalk originated in Remote Terminals can overwhelm the transmission on longer lines in a disadvantageous topology, as shown in FIG. 1, when the transmission origin from a Central Office. This problem could reduce data rates of less privileged users in such a way that only a limited set of services can be provided.
Crosstalk interference in a receiver of interest depends basically on two factors: the total transmitted Power Spectral Densities (PSDs) of all users except the user of interest and the coupling function from the transmitters to the receiver of interest.
Power Spectral Density (PSD) describes how the power of a signal is distributed with frequency. However, it should be noted that in the following description the PSD of a signal on a tone is approximated to the power carried by the signal.
There is no possible way to easily manipulate crosstalk gains in a binder, but it is however feasible to design the PSDs of the users in order to minimize crosstalk and maximize the data rates of the system. A strategy to optimize data rate, power and reach against each other is Dynamic Spectrum Management (DSM). DSM allows adaptive allocation of spectrum to various users in a multi-user environment as a function of the physical channel demographics to meet certain performance metrics. Application of DSM in present networks does not need any kind of new infrastructure and takes advantage of the plant as it is to intelligently perform management in the network.
However, finding an optimal solution for DSM problems is of high complexity. Due to power constraint, putting power on one tone affects the remaining power budget for the other tones on the same line. At the same time the power on one tone has a direct impact, due to crosstalk, to the performance on other lines, too. Therefore, the power on a tone affects not only the line the tone is used on, but all lines at all tones.
There are two approaches for the DSM in DSL systems: Rate Maximization Problem (RMP) and Power Minimization Problem (PMP). Thus, the RMP approach focuses on maximizing the data rates of the system given a power budget, whereas the PMP approach focuses on minimizing the power of the system guaranteeing a minimum data rate.
Now, consider a system with N users and K tones. A tone is a predetermined frequency range as with all multi-tone-based communication systems and different tones are presumed not to interfere with one another. The power of a user n on tone k used for transmission is denoted by pnk. The power of all users across all tones used for transmission is expressed by
      P          (              N        ×        K            )        =      [                                        p            1            1                                    …                                      p            1            K                                                ⋮                          ⋱                          ⋮                                                  p            N            1                                    …                                      p            n            k                                ]  P is a matrix, in which the upper left-corner element will denote the power of user 1 on the first tone. The lower right-corner element will denote the power of the N-th user on tone K. One row of P, which will be referred to by Pn, will represent the PSD of user n across all tones, i.e. Pn=[pn1, pn2, . . . , pnK-1, pnK]. One column of P, which will be referred to by Pk, will represent the PSD of all users across one tone, i.e. Pk=[p1k, p2k, . . . , pN-1k, pNk].
The RMP focuses on finding the maximum data rate allowed with a limited power budget for each user in a system. It can be formulated as the task of finding a given matrix P as described above such that the data rate of a given user is maximized while all other users in the network achieve a minimum desired data rate Rnmin respectively, while a limited power budget for each user is respected. The limited power budget for each user could also be expressed as there exist a maximum allowed transmit power of each user. In fact, in DSL standards PSD masks are defined that limit the transmit PSDs, which in turn limits the allowed transmit power of a user. The RMP has been the main research focus in recent DSM studies. In the following four well-known methods suited for solving the RMP will be discussed.
Firstly, a method called Optimal Spectrum Balancing (OSB) assumes convexity of the data rate region. OSB introduces Lagrange variables to formulate the problem mathematically and to be able to decouple the problem across frequency by means of dual decomposition and solves a per-tone maximization to come up with results said to be optimal for the RMP. However, it needs centralized processing and enjoys high complexity. Furthermore, it is only feasible for networks of a maximum of four users. The OSB algorithm is described in “Optimal Multi-user Spectrum Management for Digital Subscriber Lines”, Cendrillon et al, Proc. IEEE International Conference on Communications (ICC), Paris, 2004, pp. 1-5. The OSB method is also disclosed in the patent application EP1492261.
Secondly, an iterative version of the OSB method called Iterative Spectrum Balancing (ISB) method is disclosed in “Iterative Spectrum Balancing for Digital Subscriber Lines”, Cendrillon et al, IEEE International Conference on Communications (ICC), 2005, pp. 1937-1941. It can be interpreted as a middle-ground between some of the most advantageous aspects of IWF (described below) and OSB. From IWF it inherits its iterative nature and from OSB the use of Lagrange variables, dual decomposition and a weighted rate-sum. It has reduced complexity. Hence, ISB is feasible for larger networks and provide near-optimal results. However, it is a centralized solution as OSB.
Thirdly, the algorithm called Successive Convex Approximation for Low-Complexity (SCALE) utilizes a convex approximation of the original non-convex objective function and iterates through the function until this approximation is as close as possible to the original formulation. As OSB, it also uses Lagrange variables and a weighted rate-sum. It enjoys distributed implementation, low complexity and near optimal performance. The SCALE algorithm is described in “Low-Complexity Distributed Algorithms for Spectrum Balancing in Multi-User DSL Networks”, Papandriopoulos et al, 2005.
Lastly, the Iterative Water-filling (IWF) algorithm is one of the first published spectral optimization algorithms. By proper formulation of the objective function both RMP and PMP can be addressed. For the RMP the IWF algorithm uses the water-filling solution iteratively across the network with each user utilizing a power budget to achieve a maximum data rate. For the PMP the IWF algorithm uses the water-filling solution iteratively across the network with each user utilizing the minimum power necessary to achieve a minimum data rate. Iterative water-filling employs an iterative procedure whereby each transmitter applies the classical water-filling solution, i.e. increases or decreases its own power allocation, in turn until a convergence point is reached. It enjoys low complexity and autonomous implementation, i.e. the processing is distributed in the network. The IWF algorithm is disclosed in “Distributed multiuser Power Control for Digital Subscriber Lines,” Yu et al, IEEE Journal on Selected Areas of Communications, vol. 20, pp. 1105-1115, 2002.
The PMP problem has not been addressed as often as the RMP problem. The PMP can be formulated as the task of finding a set of optimized PSDs, i.e. a given combination of power allocations in the P matrix, across all tones as to minimize total power allocated in the system such that a given set of minimum required data rates is achieved. That is,
                              P          =                      arg            ⁢                                                  ⁢                                          min                P                            ⁢                                                ∑                  n                                ⁢                                  P                  n                  tot                                                                    ⁢                                  ⁢                              P            n            tot                    =                                    ∑              k                        ⁢                          p              n              k                                      ⁢                                  ⁢                              such            ⁢                                                  ⁢            that            ⁢                                                  ⁢                          R              n                                ≥                                    R              n              min                        ⁢                                                  ⁢            and            ⁢                                                  ⁢                          P              n              tot                                ≤                                    P              n              max                        ⁢                          ∀              n                                                          (        1        )            in which the minimum required data rates Rnmin are used as markers for the optimized PSDs. Further, Pntot is the total allocated power of user n across all tones, i.e. the sum of all elements in vector Pn. Pnmax is the maximum allowed power of user n across all tones and Rn is the achieved data rate for user n.
In order to solve a problem an objective-function associated with the nature of the problem can be used. The objective-function determines how well a given solution solves the problem. The objective-function of the PMP (1) can be written as a weighted power sum minimization with a given set of weighting factors wn to be determined properly,
                              P          =                      arg            ⁢                                                  ⁢                                          min                                  P                  ^                                            ⁢                                                ∑                  n                                ⁢                                                      w                    n                                    ⁢                                      P                    n                    tot                                                                                      ⁢                                  ⁢                                            such              ⁢                                                          ⁢              that              ⁢                                                          ⁢                              R                n                                      ≥                                          R                n                min                            ⁢                                                          ⁢              and              ⁢                                                          ⁢                              P                n                tot                                      ≤                                          P                n                max                            ⁢                              ∀                n                                              ,                                    (        2        )            in which wn is the weight or priority of user n. The sum of the weights of all users is constant,
                    ∑        n            ⁢              w        n              =    C    ,      C    =          constant      .      
The OSB, ISB and SCALE methods would need additional steps of calculations for solving the PMP as expressed in equation (2). Hence, the complexity would increase and the convergence speed would decrease which would make them unsuitable for solving the PMP.
Even though the IWF method was introduced as one way to solve the RMP, the IWF method is highly sub-optimal for this purpose because it does not take the impact of changes onto other lines into account.